package nk.dp;

import java.util.Scanner;

public class AB40 {


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int V = scanner.nextInt();
        int[][] dp1 = new int[n + 1][V + 1];
        int[][] dp2 = new int[n + 1][V + 1];

        int[] vol = new int[n + 1];
        int[] wei = new int[n + 1];

        for (int i = 1; i <= n ; i++) {
            vol[i] = scanner.nextInt();
            wei[i] = scanner.nextInt();
        }

        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= V; j++) {
                if (j < vol[i]) { //当前背包容量放不下第i个物品，价值就等于容量为j的背包装前i-1个物品的价值
                    dp1[i][j] = dp1[i-1][j];
                } else { //能装下第i个物品，选择装或不装的较大者
                    dp1[i][j] = Math.max(dp1[i-1][j], dp1[i-1][j-vol[i]] + wei[i]);
                }
            }
        }
        System.out.println(dp1[n][V]);

        for (int i = 0; i <= n ; i++) {
            for (int j = 0; j <= V ; j++) {
                dp2[i][j] = Integer.MIN_VALUE; //初始化无法正好填满背包的情况值为int最小值
            }
        }
        dp2[0][0] = 0;

        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= V ; j++) {
                if (j < vol[i]) {
                    dp2[i][j] = dp2[i-1][j];
                } else {
                    dp2[i][j] = Math.max(dp2[i-1][j], dp2[i-1][j-vol[i]] + wei[i]);
                }
            }
        }
        System.out.println(dp2[n][V] < 0 ? 0 : dp2[n][V]);
    }


}
